package com.lw.leetcode.greedy.c;

import com.lw.test.util.Utils;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 1326. 灌溉花园的最少水龙头数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/7 14:29
 */
public class MinTaps {

    public static void main(String[] args) {
        MinTaps test = new MinTaps();

        // 1
//        int n = 5;
//        int[] ranges = {3, 4, 1, 1, 0, 0};

        // 1
//        int n = 1;
//        int[] ranges = {100,100};

        // -1
//        int n = 3;
//        int[] ranges = {0, 0, 0, 0};

        //
        int n = 10000;
        System.out.println(n);
        int[] ranges = Utils.getArr(n + 1,0, 20);

        int i = test.minTaps(n, ranges);
        System.out.println(i);
    }

    public int minTaps(int n, int[] ranges) {
        int length = ranges.length;
        int item = 0;
        int c = 1;
        int next = 0;
        int[][] arr = new int[length][2];
        for (int i = 0; i < length; i++) {
            arr[i][0] = i - ranges[i];
            arr[i][1] = i + ranges[i];
        }
        Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));
        for (int i = 0; i < length; i++) {
            int st = arr[i][0];
            if (st > next) {
                return -1;
            }
            if (st > item) {
                c++;
                item = next;
            }
            next = Math.max(next, arr[i][1]);
            if (next >= n) {
                return c;
            }
        }
        return -1;
    }

}
